package basic.sort.list;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;
import java.util.Stack;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.list
 * @since JDK1.8
 */
public class IsPalindromeList {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    // 栈
    // 将节点一一添加到栈中，然后一一弹出进行比较
    private static boolean stackPalindrome(Node head) {
        // 栈
        Stack<Node> stack = new Stack<>();
        // 临时节点
        Node node = head;
        // 循环添加节点到栈中
        while (node != null) {
            stack.add(node);
            node = node.next;
        }
        node = head;

        // 从栈中弹出节点，一一比较
        while (!stack.isEmpty()) {
            if (node.value != stack.pop().value) {
                return false;
            }
        }

        return true;
    }

    // 不使用额外空间
    // 先通过快慢指针找到中点，然后对后半段链表反转
    // 最后是需要将链表还原
    private static boolean noExtraSpace(Node head) {
        if (head == null || head.next == null) {
            return true;
        }

        // 找到中点
        // 快慢指针
        Node slow = head;
        Node fast = head;
        // 循环找到中点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 反转后半段链表
        // 辅助节点
        Node sup = null;
        // 初始条件
        fast = slow.next;
        slow.next = null;
        // 循环反转
        while (fast != null) {
            sup = fast.next;
            fast.next = slow;
            slow = fast;
            fast = sup;
        }
        // 保存节点
        sup = slow;

        // 循环比对前半段和后半段的值
        fast = head;
        while (slow != null && fast != null) {
            if (slow.value != fast.value) {
                return false;
            }

            slow = slow.next;
            fast = fast.next;
        }

        // 还原链表
        slow = sup.next;
        sup.next = null;
        while (slow != null) {
            fast = slow.next;
            slow.next = sup;
            sup = slow;
            slow = fast;
        }

        return true;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {

        Node head = null;
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(1);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(2);
        head.next.next.next.next = new Node(1);
        printLinkedList(head);
        System.out.print(stackPalindrome(head) + " | ");
        System.out.println(noExtraSpace(head) + " | ");
        printLinkedList(head);
        System.out.println("=========================");

    }
}
